1. Field of the Invention
The present invention relates to a program translating apparatus in a computer having a limited and finite number of registers. In particular, the present invention relates to register allocation in a program translating process adapted to a compiler or an interpreter.
2. Description of the Related Art
A register allocation technique using a graphically coloring method as described in Reference 1 (G. J. Chaitin, M. A. Auslander, A. K. Chander, J. Cocke, M. E. Hopkins and P. W. Markstein, "Register Allocation via Coloring", Computer Language 6, pp. 47-37 (1981)) is one of register allocation techniques on conventional compilers. This type of technique performs register allocation through a process in which an interference graph is generated on the basis of judgment as to whether registers interfere with one another over all the ranges of existence thereof. Each node of the interference graph is colored to form one-to-one correspondence between colors and registers actually existing. Therefore, a case where some registers cannot be allocated, though an allocatable range actually exists in the register, often occurs because the range of existence of a variable cannot be completely put in the allocatable range. There arises a disadvantage in that object codes generated are poor in efficiency. Although the time required for computing is relatively short if the number of registers is sufficient, the overhead required for re-computing becomes very large because the number of nodes of the interference graph as subjects of register allocation must be reduced by insertion of "spill" codes if the number of registers which can be used is insufficient.
According to an allocation technique as described in Reference 2 ("Allocation by Priority-based Coloring", Proceedings of the ACMSIGPLAN Symposium on Compiler Construction, pp. 222-232 (Jun. 17-22, 1984)), the disadvantage of the technique of the above Reference 1 is eliminated by separating the range of existence of a variable impossible of attaining of thorough coloring into ranges existence in the case where coloring based on a limited number of colors on the interference graph is impossible. The technique of the Reference 2, however, has a disadvantage in that a long time is required for reconstructing a new interference graph by adding nodes corresponding to the newly allocated ranges of existence of the variable to the original interference graph and for performing re-computing of priority, coloring and the like on the basis of the new interference graph. In particular, with respect to a range of existence which is low in priority such that it cannot be allocated to the last, wasteful separation is repeated. Further, in the technique of the Reference 2, a loop is used as a subject of weighing when priority is computed. There is, however, a difference in frequency of use between basic blocks based on condition branches (conditional jumps) in actual source codes. Accordingly, the case where priority cannot be correctly computed often occurs.
According to a technique described in Japanese Patent Unexamined Publication No. Hei. 1-103742, the problem in the above Reference 2 is solved by computing the priority of the ranges of existence so as to be nearer to the approximation of the frequency in use under the consideration of conditional branches (conditional jumps) in conditional statements (if statements) while separating exclusively the ranges of existence as subjects of allocation on the basis of the technique of the Reference 2 to suppress the increase in the computing time due to wasteful separation.
In any one of the aforementioned techniques, a range of existence of a variable is totally allocated to a register if the register can be allocated for the whole range of existence of the variable, and the efficiency in codes generated based on the existence of the variable in the register is better than the efficiency in codes generated based on the existence of the variable in a memory. For this reason, a part of a range of existence which is low in frequency in use occupies one register in the case where there is a difference in frequency in use between parts of the range of existence. There arises a disadvantage in that optimum codes cannot be always generated.